1. Field of the Invention
A method and device for scheduling a plurality of events.
2. Prior Art
Scheduling in general, including scheduling of a manufacturer""s supply chain for time-sensitive and complex manufacturing operations while satisfying resource, geographic, temporal and operating constraints, is a highly complex, non-linear problem that falls into a notoriously difficult mathematical class of hard to solve problems (technically, xe2x80x9cNP-hardxe2x80x9d). Manual scheduling, even when computer-assisted, is expensive in terms of time, manpower, and funds and produces far less than optimal scheduling of critical resources for critical manufacturing requirements.
The prior art methods for automating supply chain scheduling for manufacturing systems produce solutions that are xe2x80x9cadequatexe2x80x9d (however defined), but often far from optimal, sometimes leading to bottlenecks, excess supply inventories, supply shortages, or temporal disconnects, all of which may disrupt the manufacturing process and drive up unit production costs. This is especially so for manufacturing of leading edge products and/or where large numbers of companies are involved in the manufacturing process. Automated real-time and optimal supply chain scheduling for manufacturing systems would increase scheduling (and hence manufacturing) effectiveness and reduce unit production costs by avoiding the negative consequences of non-optimal scheduling.
Past attempts at mathematically optimal scheduling have usually employed a single promising artificial intelligence (AI) or operations research (OR) methodology in a xe2x80x9cbrute forcexe2x80x9d computational assault on the problem. Each such methodology has weaknesses relative to solving large-scale, computationally complex supply chain scheduling problems. Generally speaking, manufacturing supply chain scheduling problems exhibit the following characteristics: (a) a large number of constrained resources that must be scheduled in order to accomplish the manufacturing process; (b) complexity in terms of geographic and temporal geometry; (c) time sensitive actions to be scheduled; and (d) present a large problem/solution space typically proportional to m!, where m is the number of supply chain events to be scheduled within the problem time horizon with worst-case single algorithm solution times that are exponential in m.
Computational complexity theory (CCT) deals with the time (T) it takes an algorithm implemented in a computer program to solve a problem. Typically, the computational complexity of a problem is classified according to the time needed to solve it on a Turing Machine (TM), defined as a finite state machine with an infinite read-write tape. T is expressed as a function of n, where n is a measure of the size of the input or the number of inputs to the TM for solving the problem. In CCT, T as a function of n, T(n), is generally expressed in xe2x80x9corder-of-magnitudexe2x80x9d form O (f(n)). T(n)=O (f(n)) means there exists constants k and n such that
T(n)xe2x89xa6k|f(n)| for nxe2x89xa7n0xe2x80x83xe2x80x83(1)
For example, suppose that solution time for a problem is given by T(n)=5n+2. In this case, T(n)=O(n) since 5n+2xe2x89xa66n for nxe2x89xa72 (i.e.,f (n)=n, k=6, and n0==2). If T (n) is a polynomial of the form
T(n)=aini+aixe2x88x921nixe2x88x921+. . . +a1n+a0xe2x80x83xe2x80x83(2)
then T(n)=O(ni); i.e., all constants and low-order terms are ignored. Thus for T(n)=O (n2), a doubling of the size of the problem quadruples the solution time required. It is common and useful to classify problems according to their order of magnitude time complexities.
A problem is polynomial or polynomial time if its solution time on a TM is given by T (n)=O (nb) for some constant b: solution time is constant if b=0, linear if b=1, quadratic if b=2, etc. Solution time is exponential if T(n)=O(bh(n)) for constant b and polynomial h(n). For large n, the order of magnitude complexity of a problem can make a dramatic difference in solution times.
The class of problems P that are solvable in polynomial time are considered tractable because they can usually be solved in a reasonable amount of time for reasonable size inputs. Problems that cannot be solved in polynomial time are generally considered intractable or xe2x80x9chardxe2x80x9d problems because as the size of the input representing the problem increases, solutions become computationally infeasible on even the fastest computers.
On the other hand, the class NP (which stands for nondeterministic polynomial) consists of all problems that are solvable in polynomial time on a nondeterministic TM, where xe2x80x9csolvablexe2x80x9d in this case does not have the usual meaning. A nondeterministic TM does not systematically solve a problem as does a deterministic TM, but instead guesses a solution (hence the term nondeterministic) and then checks its correctness. A given problem is said to be solvable in polynomial time on a nondeterministic TM if a nondeterministic TM can check the correctness of its guessed solution in polynomial time. Unfortunately, worst case times for systematically (deterministically) solving NP problems in the usual sense of the term are often exponential. The so-called xe2x80x9csatisfiabilityxe2x80x9d problem is an example of an NP problem which may be stated as follows: determine whether there exists an assignment of values to a set of n boolean variables such that a given set of constraints over the variables is met.
The class NP includes the class P because any problem solvable in polynomial time on a deterministic TM is also polynomial solvable on a nondeterministic TM. If all NP problems are polynomial solvable on a deterministic TM, then P=NP. Although many problems in NP seem much harder than the problems in P (e.g., satisfiability problems) no one has yet proven that Pxe2x89xa0NP. Several decades ago, the satisfiability problem was proved to have the property that every other problem in NP can be reduced to it in polynomial time. This means that if the satisfiability problem is polynomial solvable, then every problem in NP is polynomial solvable, and if some problem in NP is intractable, then the satisfiability problem must also be intractable. Since 1971, other problems have been shown to be equivalent to the satisfiability problem. This set of equivalent problems is called the set of xe2x80x9cNP-completexe2x80x9d problems, and has the property that if any one of the problems in that set is in P, then all NP problems are in P and P=NP. Thus, NP-complete problems are the hardest problems in NP (and are therefore sometimes also called NP-hard), or said another way, they set the upper bound on xe2x80x9chardnessxe2x80x9d for NP problems.
The fastest known algorithms for systematically solving these problems have worst case solution times that are exponential in the size n of the problem. Finding a worst-case polynomial-time solution to one of them would be a major breakthrough in computer science. However, despite the fact that the worst-case or upper-bound solve times for NP problems are exponential in n, in actual practice, solve times are often shorter than worst-case.
In summary, the general scheduling problem has been shown to be an NP-hard combinatorial optimization problem. A combinatorial optimization problem consists of finding, from among a finite set of alternatives, one that optimizes the value of a given objective function. Scheduling problems are satisfiability problems, and thus NP-hard problems too, because they seek to assign boolean values to requested events (i.e., decide whether they are scheduled or not) such that a given set of constraints are met. There remains a need for a method and device for finding an optimal solution to the multi-task scheduling problem in real time.
It is a first object of the invention to provide means for obtaining an optimal solution to a multi-task scheduling problem.
It is a further object of the invention to provide a method which may be used in a computer environment to find a solution to a multi-task scheduling problem.
It is another object of the invention to provide a computer readable medium bearing instructions which cause a computer system to provide an optimal solution to a scheduling problem.
It is yet a further objective of the invention to provide means for accomplishing the above objectives in minimal time.
The above objectives are met by applying artificial intelligence to partition or fragment a multi-task scheduling problem into a set of mathematically independent scheduling problems. An artificial intelligence xe2x80x9cshellxe2x80x9d then selects one of a plurality of algorithms, which will provide an optimal solution, in minimal time, for each individual scheduling sub-problem. The process is repeated for each sub-problem comprising the set of mathematically independent scheduling sub-problems. The individual solutions are then combined or defragmented to provide an optimal solution to the scheduling problem as a whole.